package com.arron.algorithm.leetcodetop100.技巧.原地hash;

import java.util.HashSet;
import java.util.Set;

public class 缺失的第一个正数 {




    //使用自己作为hash表做映射
    public int firstMissingPositive_plus(int[] nums) {
        int len = nums.length;


        for (int i = 0; i < len; i++) {

            while (nums[i] >=1 && nums[i]<= len && nums[nums[i]-1] !=nums[i]){
                int temp = nums[nums[i]-1];
                nums[nums[i]-1] = nums[i];
                nums[i] = temp;
            }

        }

        for (int i = 0; i <len ; i++) {
            if (nums[i] != i+1){
                return i+1;
            }
        }

        return len+1;
    }


    //使用hash来存储
    public int firstMissingPositive(int[] nums) {

        int len =  nums.length;

        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < len; i++) {
            set.add(nums[i]);
        }

        for (int i = 1; i <=len ; i++) {
                if (!set.contains(i)){
                    return i;
                }
        }

        return  len+1;
    }

}
